package 经典排序;

import com.alibaba.fastjson.JSON;

import java.util.PriorityQueue;

public class JZ40最小的k个数 {

    /**
     * 输入整数数组 arr ，找出其中最小的 k 个数。
     * 例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
     *
     * 示例 1：
     * 输入：arr = [3,2,1], k = 2
     * 输出：[1,2] 或者 [2,1]
     * 示例 2：
     * 输入：arr = [0,1,2,1], k = 1
     * 输出：[0]
     *  
     * 限制：
     * 0 <= k <= arr.length <= 10000
     * 0 <= arr[i] <= 10000
     */

    public int[] getLeastNumbers(int[] arr, int k) {

        if(arr.length==0){
            return new int[]{};
        }

        if(k==0){
            return new int[]{};
        }

        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>((o1,o2)->o2-o1);

        for (int i = 0; i < k; i++) {
            priorityQueue.add(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            if(arr[i]<priorityQueue.peek()){
                priorityQueue.poll();
                priorityQueue.add(arr[i]);
            }
        }

        int[] result=new int[k];

        for (int i = 0; i < result.length; i++) {
            result[i]=priorityQueue.poll();
        }

        return result;
    }

    public static void main(String[] args) {
        JZ40最小的k个数 jz=new JZ40最小的k个数();
        int[] arr={3,2,1};
        int[] result = jz.getLeastNumbers(arr, 2);
        System.out.println(JSON.toJSONString(result));
    }

}
